package classic;

public class Misc {
	
	public static void main(String[] args) {
		//System.out.println(findMedianOfTwoEqualLengthSortedArray(0, arr1.length-1, 0, arr2.length-1));
		//System.out.println(findLongestCommonSubStringDP3Strings());
		System.out.println(findMeInInfiniteSortedArray());
	}
	
	static int[] arr1 = {6,7,21,25,30}, arr2 = {1,2,3,4,5};
	static int findMedianOfTwoEqualLengthSortedArray(int i, int j, int l, int m){
		int ret = 0;
		int idx1 = (int) Math.ceil((j-i)/2);
		int idx2 = (int) Math.ceil((m-l)/2);
		int m1 = arr1[idx1];
		int m2 = arr2[idx2];
		if( j-i == 0){
			ret =  arr1[i];
		}
		else if( j-i ==1){
			ret =  Math.max(Math.min(arr1[i], arr2[l]), Math.min(arr1[j], arr2[m]));
		}
		else if(m1 ==m2 ) return m1; //or m2
		else if(m1 < m2) {
			//search between m1: arr1.len and 0:m2 in arr2. 
			ret = findMedianOfTwoEqualLengthSortedArray(idx1+1, j, l, idx2);
		}else {
			ret = findMedianOfTwoEqualLengthSortedArray(i, idx1, idx2+1, m);
		}
		return ret;
	}
	
//	static int findKthMinElementInUnSortedArray(){
		
	//}
	/**
	 * Q: Longest common substring
	 * find the longest common suffix of all possible prefixes of string. Max of longest common suffix would be max common substring
	 * @return
	 */
	//brute force
	static String str1 = "dababc";
	static String str2 = "abxaba";
	static int findLongestCommonSubString(){
		int max = 0;
		for(int i=str1.length()-1;  i>=0 ; i--){  
			for(int j=str2.length()-1; j>=0 ;j--){  
				int count =0;
				while(str1.charAt(i+count) == str2.charAt(j+count)){   
					max = Math.max(++count, max);
					if(i+count == str1.length() || j+count == str2.length()) break;
				}
			}
		}
		return max;
	}
	
	//we need to find out longest suffix of all the prefix(not proper prefix, so prefix could be equal to string itself) of two strings
	//looking at above code we could optimize above while loop where we could precalculate suffix of differnt prefix 
	// lcs(Sm, Tn) = lcs(Sm-1, Tn-1) + 1 if Sm = Tn else 0
	static int[][] dp_lcst = new int[str1.length()][str2.length()];
	static int findLongestCommonSubStringDPBottomUp(){
		int max = 0;
		for(int i=0; i<str1.length(); i++){
			for(int j=0; j<str2.length(); j++){
				if(str1.charAt(i) == str2.charAt(j)){
					if(i==0 || j==0) dp_lcst[i][j] = 1;
					else dp_lcst[i][j] = dp_lcst[i-1][j-1] +1;
					max = Math.max(max, dp_lcst[i][j]);
				}
			}
		}
		return max ;
	}
	
	//TODO could we find top down (memoized) DP for this
	
	//TODO use suffix array on cancatinated string and str1$str2@ and find longest consicutive prepixes from both strings
	
	//TODO find longest common substring for three strings
	static String str3 ="aababaaa";
	static int[][][] dp3str = new int[str1.length()][str2.length()][str3.length()];
	static int findLongestCommonSubStringDP3Strings(){
		int max =0;
		for(int i=0; i<str1.length(); i++){
			for(int j=0; j<str2.length(); j++){
				for(int k=0; k<str3.length(); k++){
					if((str1.charAt(i) == str2.charAt(j)) && str1.charAt(i) == str3.charAt(k)){
						if(i==0 || j==0 || k==0){
							dp3str[i][j][k] = 1;
						}else{
							dp3str[i][j][k] = 1 + dp3str[i-1][j-1][k-1];
						}
						max = Math.max(max, dp3str[i][j][k]);
					}
				}
			}
		}
		return max;
	}
	
	//Q: position of element in sorted array of infinte length
	static int findMeInInfiniteSortedArray(){
		int[] arr = new int[]{1,2,3,4,5,6,7,8,9,12,20,30,40,50,51,54,55,56};
		int low = 0;
		int high = 1;
		int findMe = 12;
		while(arr[high] <=findMe){
			low = high;
			high = high*2;
		}
		int idx = -1;
		while(low<=high){
			int mid = (low+high)/2;
			if(arr[mid] == findMe){
				idx = low;
				break;
			}
			if(findMe>arr[mid]){
				low = mid+1;
			}else{
				high = mid;
			}
		}
		return idx;
	}

}
